\section{Conclusions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:cc}

We present a pattern-matching library for C++ provides fairly standard
pattern-matching facilities. Our solution is 
non-intrusive and can be retroactively applied to any polymorphic or tagged 
class hierarchy. It also provides a uniform notation to these different 
encodings of algebraic and extensible hierarchical data types in C++.

We generalize n+k patterns to arbitrary expressions by letting the user define 
the exact semantics of such patterns. Our approach is more general than traditional approaches 
as it does not require an
equational view of such patterns. It also avoids hardcoding the 
exact semantics of n+k patterns into the language. 

We used the library to rewrite existing code that relied heavily on the 
visitor design pattern.
Our pattern matching code was much shorter (both source and object code), 
simpler, easier to maintain, comprehend, and faster. 
This confirmed our view of the visitor pattern as a clever workaround,
rather than a good solution to a fundamental problem.
The library approach was essential 
for experimentation in the context of real programs and for delivering 
performance comparable with or superior to conventional techniques in the 
context of industrial compilers.

The work presented here is only the beginning of our research on pattern 
matching for C++. We would like to experiment with other kinds of patterns, 
including those defined by the user; look at the interaction of patterns with 
other facilities in the language and the standard library; make
views less ad hoc etc. For example, standard containers in C++ do not have the 
implicit recursive structure present in data types of functional languages and 
viewing them as such with views would incur significant overheads. We will
experiment with very general patterns as first-class citizens.

Our generalization of n+k patterns depends on the properties of types involved 
in the expression. This should let us experiment not only with generic 
functions, but also with their generic inversions in the form of solvers. As 
more C++11 features become available in compilers it will also be interesting to 
look at how use of these features affects the ease of use, performance, 
readability, writability and debugging of the library and the user code that 
uses it.

Type switching is an open alternative to the visitor design pattern that overcomes 
the restrictions, inconveniences, and difficulties in teaching and using 
visitors. Our implementation significantly
outperforms the visitor design pattern in most cases and roughly equals it otherwise.
This is the case even though we use a library implementation and highly optimized
production-quality compilers. An important benefit of our solution is that it does not 
require any changes to the \Cpp{} object-model or require any computations at load 
time.

To provide a complete solution, we use the same syntax for closed sets of types, where our
performance roughly equals the equivalent built-in features in functional languages,
such as Haskell and OCaml.

We prove the uniqueness of vtbl-pointers in the presence of RTTI. This is 
potentially useful in other compiler optimizations that depend on the 
identity of subobjects. Our memoization device can also become valuable in 
optimizations that require mapping run-time values to execution paths, 
and is especially useful in library setting.

We describe three techniques that can be used to implement type switching, type 
testing, pattern matching, predicate dispatching, and other facilities that 
depend on the run-time type of an argument as well as demonstrate their efficiency.

The \emph{Memoization Device} is an optimization technique that maps run-time values 
to execution paths, allowing to take shortcuts on subsequent runs with the same 
value. The technique does not require code duplication and in typical cases adds 
only a single indirect assignment to each of the execution paths. It can be 
combined with other compiler optimizations and is particularly suitable for use 
in a library setting.

The \emph{Vtable Pointer Memoization} is a technique based on memoization device that 
employs uniqueness of virtual table pointers to not only speed up execution, but 
also properly uncover the dynamic type of an object. This technique is a 
backbone of our fast type switch as well as memoized dynamic cast optimization.

The \emph{TPL Dispatcher} is yet another technique that can be used to 
implement best-fit type switching on tagged classes. The technique has its pros 
and cons in comparison to vtable pointer memoization, which we discuss in the paper.

These techniques can be used in a compiler and library setting, and support well 
separate compilation and dynamic linking. They are open to class extensions and 
interact well with other \Cpp{} facilities such as multiple inheritance and 
templates. The techniques are not specific to \Cpp{} and can be adopted in other 
languages for similar purposes.

Using the above techniques, we implemented a library for efficient type switching 
in \Cpp{}. We used the library to rewrite existing code that relied heavily on 
visitors, and discovered that the resulting code became much shorter, simpler, 
and easier to maintain and comprehend.

We used the library to rewrite existing code that relied heavily on 
visitors, and discovered that the resulting code became much shorter, simpler, and easier 
to maintain and comprehend.
